package experiment2.matrixchains;

import java.util.Random;
import java.util.Scanner;

public class MatrixChains {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Random random = new Random();

        while (true) {
            System.out.print("请输入数组的个数:");
            int length = scanner.nextInt() + 1;
            int[] p = new int[length];

            int i;
            for (i = 0; i < length; ++i) {
                p[i] = random.nextInt(100) + 1;
            }

            for (i = 0; i < length - 1; ++i) {
                System.out.print(p[i] + "x" + p[i + 1] + " ");
            }

            System.out.println();
            int[][] m = new int[length][length];
            int[][] s = new int[length][length];

            System.out.println("最优值为： " + matrixChains(p, m, s));
            traceback(1, length - 1, s);
            System.out.println();
            System.out.println();
        }
    }

    public static int matrixChains(int[] p, int[][] m, int[][] s) {
        int n = p.length - 1;

        for (int r = 2; r <= n; ++r) {
            for (int i = 1; i <= n - r + 1; ++i) {
                int j = i + r - 1;
                m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
                s[i][j] = i;

                for (int k = i + 1; k < j; ++k) {
                    int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if (t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
            }
        }

        return m[1][n];
    }

    public static void traceback(int i, int j, int[][] s) {
        if (i == j) {
            System.out.print("A" + i);
        } else {
            System.out.print("(");
            traceback(i, s[i][j], s);
            traceback(s[i][j] + 1, j, s);
            System.out.print(")");
        }

    }
}
